package LeetCode;

public class SQRT {
  
//this is clear, remember it
  public int sqrt2(int x)
  {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    if (x <= 1) return x;

    int left = 0, right = x, mid;

    while ((right - left) > 1) {
      mid = left + (right - left) / 2;

      if (mid == x / mid)
        return mid;
      else if (x / mid < mid)
        right = mid;
      else
        left = mid;
    }

    return left;
  }

  // binary search
  // pass both
  public int sqrt(int x) {
    // Start typing your Java solution below
    // DO NOT write main() function
    if (x == 0)
      return 0;
    if (x <= 2)
      return 1;
    int s = 2;
    int prev = 1;
    while (!(s <= x / s && (s + 1) > x / (s + 1))) {
      if (s > x / s) {
        s = prev + (s - prev) / 2;
      } else {
        prev = s;
        s = s * s;
      }
    }

    return s;
  }
  
  public int sqrt1(int x)
  {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    double ans = x;

    while (Math.abs(ans * ans - x) > 0.0001) {
      ans = (ans + x / ans) / 2;
    }

    return (int) ans;
  }
  
  

  /**
   * @param args
   */
  public static void main(String[] args) {
    // TODO Auto-generated method stub

  }

}
